package com.leetcode.leetcode1;

/**
 * @program: 最长回文子串
 * @author: luhd
 * @create: 2021-08-16
 */

/**
 *   给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *   示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 */
public class Practice05 {
    public static void main(String[] args) {
        /*
            解题思路：遍历每一个字符，从中间向两边扩展，两边相同就继续扩展，要注意回文子串是基数还是偶数
            写一个辅助方法判断当前字符向左右两边扩展
         */
        //先将字符串变为数组
        String s = "babad";
        String s1 = longestPalindrome(s);
        System.out.println(s1);

    }
    public static String longestPalindrome(String s){
        int strLen = s.length();
        if(strLen <2) return s;
        // 把字符串中的每一个字符都当作回文串的中心
        int left = 0;
        int right = 0;
        int len =1;
        int maxStart = 0;
        int maxLen = 0;
        for (int i = 0; i < strLen; i++) {
            left = i-1;
            right = i+1;
            while(left>=0&&s.charAt(left)==s.charAt(i)){
                len++;
                left--;
            }
            while(right<strLen&&s.charAt(right)==s.charAt(i)){
                len++;
                right++;
            }
            while(left>=0&&right<strLen&&s.charAt(left)==s.charAt(right)){
                len+=2;
                left--;
                right++;
            }
            if(len > maxLen){
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart+1,maxLen+maxStart+1);
    }
}
